package leetcode.剑指offer.前40;

import leetcode.剑指offer.pojo.TreeNode;
import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/10/10 16:45
 * @description：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
 */
public class 剑指_26_树的子结构 {
    @Test
    public void test() {
        Solution solution = new Solution();
        TreeNode A = new TreeNode(3, new TreeNode(4, new TreeNode(1), new TreeNode(2)), new TreeNode(5));
        TreeNode B = new TreeNode(4, new TreeNode(1), null);
        System.out.println(solution.isSubStructure(A, B));
    }

    class Solution {
        public boolean isSubStructure(TreeNode A, TreeNode B) {
            if (A == null || B == null) return false;
            return isSubStructure0(A, B)
                    || isSubStructure(A.left, B)
                    || isSubStructure(A.right, B);
        }

        public boolean isSubStructure0(TreeNode A, TreeNode B) {
            if (B == null) return true;
            if (A == null || A.val != B.val) return false;
            return isSubStructure0(A.left, B.left) && isSubStructure0(A.right, B.right);
        }
    }
}
